#include "DGraph.h"

using namespace std;

DGraph::DGraph() {
	clear();
	_G = GRAPH();
	_VL = VertexList();
	_N = 0;
	//	_M = 0;
	_tree = DTree();
	//	_NTE = NTEList();
	_longNTE = LNTEList();
	_shortNTE = SNTEList();

	opt = false;
}

DGraph::DGraph(int N) {
	clear();
	_G = GRAPH(N, InOutEdgeList());
	_VL = VertexList(N);
	_N = N;
	//	_M = 0;
	for (int vid = 0; vid < _N; ++vid) {
		Vertex& vex = _VL[vid];
		vex._ID = vid;
		//vex._IntBeg = -1;
		//vex._IntEnd = -1;
		vex._DFLN = -1;
		vex._SupDFLN = -1;
		vex._PreN = -1;
		vex._TopoID = -1;
		vex._visited = false;
		_VL[vid] = vex;

		EdgeList il = EdgeList();
		EdgeList ol = EdgeList();
		InOutEdgeList oil = InOutEdgeList();
		oil._inList = il;
		oil._outList = ol;
		_G[vex._ID] = oil;
	}
	_tree = DTree();
	//_NTE = NTEList();
	_longNTE = LNTEList();
	_shortNTE = SNTEList();
	opt = false;
}

DGraph::DGraph(istream& in) {
	clear();
	read_graph(in);
	_tree = DTree();
	//	_NTE = NTEList();
	_longNTE = LNTEList();
	_shortNTE = SNTEList();
	opt = false;
}

DGraph::DGraph(GRAPH& g, VertexList& vlist) {
	clear();
	_N = vlist.size();
	_G = g;
	_VL = vlist;
	/*
	 // compute _M
	 _M = 0;
	 for (GRAPH::iterator it=_G.begin(); it!=_G.end(); ++it)
	 {
	 _M += it->_outList.size();
	 }
	 */
	// for test
	cout << "_N=" << _N << "; _M=" << number_of_edges() << endl;
	_tree = DTree();
	//_NTE = NTEList();
	_longNTE = LNTEList();
	_shortNTE = SNTEList();
	opt = false;
}

DGraph::DGraph(/*hash_map*/map<int, vector<int> >& inlist, /*hash_map*/map<int,
		vector<int> >& outlist) {
	clear();
	int _N = inlist.size();
	_VL = VertexList(_N);
	_G = GRAPH(_N, InOutEdgeList());
	_N = _VL.size();
	for (int vid = 0; vid < _N; vid++) {
		add_vertex(vid);
	}
	/*hash_map*/
	map<int, vector<int> >::iterator hit, hit1;
	/*hash_map*/
	map<int, int> indexmap;
	vector<int> vec;
	vector<int>::iterator vit;
	int k;
	for (hit = inlist.begin(), k = 0; hit != inlist.end(); hit++, k++) {
		indexmap[hit->first] = k;
	}
	for (hit = inlist.begin(), hit1 = outlist.begin(), k = 0; hit
			!= inlist.end(); hit++, hit1++, k++) {
		vec = hit->second;
		for (vit = vec.begin(); vit != vec.end(); vit++) {
			_G[k]._inList.push_back(indexmap[*vit]);
		}
		vec = hit1->second;
		for (vit = vec.begin(); vit != vec.end(); vit++) {
			_G[k]._outList.push_back(indexmap[*vit]);
		}
	}
	//_tree = DTree();
	//	_NTE = NTEList();
	_longNTE = LNTEList();
	_shortNTE = SNTEList();
	opt = false;
}

DGraph::~DGraph() {
}

void DGraph::clear() {
	_G.clear();
	_VL.clear();
	_tree.clear();
	// _NTE.clear();
	_longNTE.clear();
	_shortNTE.clear();
	_N = 0;
	//    _M = 0;
}

void DGraph::add_vertex(int vid) {
	if (vid >= _VL.size()) {
		// insert vertices with ID less than vid
		int size = _VL.size();
		for (int i = 0; i < (vid - size + 1); i++) {
			_G.push_back(InOutEdgeList());
			Vertex vex;
			vex._ID = size + i;
			//vex._IntBeg = -1;
			//vex._IntEnd = -1;
			vex._DFLN = -1;
			vex._SupDFLN = -1;
			vex._PreN = -1;
			vex._TopoID = -1;
			vex._visited = false;
			_VL.push_back(vex);
		}
		_N = _VL.size();
	}

	// if there's already a vertex whose ID is vid, then modify it with initial values
	// if this is the new vertex insterted, then modify it also
	//cout << _G.size() << ";" << _VL.size() << ";" << _N << endl;
	Vertex vex;
	vex._ID = vid;
	//vex._IntBeg = -1;
	//vex._IntEnd = -1;
	vex._DFLN = -1;
	vex._SupDFLN = -1;
	vex._PreN = -1;
	vex._TopoID = -1;
	vex._visited = false;
	_VL[vid] = vex;

	EdgeList il = EdgeList();
	EdgeList ol = EdgeList();
	InOutEdgeList oil = InOutEdgeList();
	oil._inList = il;
	oil._outList = ol;
	_G[vex._ID] = oil;
	// Very strange behaviour: if omitting the following line,
	// when finishing this method, _N is an invalid number
	_N = _VL.size();
}

bool DGraph::add_edge(int src, int trg) {
	if (src >= _N || trg >= _N)
		return false;
	else {
		vector<int>::iterator eit;
		for (eit = _G[src]._outList.begin(); eit != _G[src]._outList.end(); ++eit)
		// check that whether the edge <src,trg> has already been added to the graph
		{
			if (*eit == trg)
				break;
		}
		if (eit == _G[src]._outList.end()) {
			_G[src]._outList.push_back(trg);
			_G[trg]._inList.push_back(src);
			//           ++_M;
		}
		return true;
	}
}

bool DGraph::delete_edge(int src, int trg) {
	if (src >= _N || trg >= _N)
		return false;
	else {
		EdgeList::iterator oit, iit;
		// erase the heading vertex src's out-going edge list
		for (oit = _G[src]._outList.begin(); oit != _G[src]._outList.end(); ++oit)
		// check that whether the edge <src,trg> has already been added to the graph
		{
			if (*oit == trg)
				break;
		}
		if (oit != _G[src]._outList.end()) { // There is such an edge (src, trg)
			_G[src]._outList.erase(oit);
			// erase the tailing vertex trg's in-going edge list
			for (iit = _G[trg]._inList.begin(); iit != _G[trg]._inList.end(); ++iit) {
				if (*iit == src)
					break;
			}
			_G[trg]._inList.erase(iit);
			//           --_M;
		}
		return true;
	}
}

int DGraph::number_of_vertices() {
	return _N;
}

int DGraph::number_of_edges() {
	//    return _M;

	EdgeList el;
	GRAPH::iterator git;
	int num = 0;
	for (git = _G.begin(); git != _G.end(); git++) {
		el = git->_outList;
		num += el.size();
	}
	return num;

}

VertexList& DGraph::get_vertices() {
	return _VL;
}

VertexList DGraph::get_vertices_withoutrefer() {
	return _VL;
}


EdgeList& DGraph::edges_from(int vid) {
	return _G[vid]._outList;
}

EdgeList& DGraph::edges_to(int vid) {
	return _G[vid]._inList;
}

vector<int> DGraph::get_roots() {
	if (!opt) {
		vector<int> r;
		//  cout << _VL.size() << endl;
		for (int vid = 0; vid < _N; ++vid) {
			if (in_degree_of(vid) == 0) {
				r.push_back(vid);
			}
		}
		return r;
	} else {
		return roots;
	}
}

int DGraph::out_degree_of(int vid) {
	if (vid >= _N) {
		return -1; // this vertex does not exist
	} else {
		return _G[vid]._outList.size();
	}
}

int DGraph::in_degree_of(int vid) {
	if (vid >= _N) {
		return -1; // this vertex does not exist
	} else {
		return _G[vid]._inList.size();
	}
}

bool DGraph::has_edge(int src, int trg) {
	EdgeList ol = _G[src]._outList;
	for (EdgeList::iterator eit = ol.begin(); eit != ol.end(); eit++) {
		if ((*eit) == trg) {
			return true;
		}
	}
	return false;
}

DGraph& DGraph::operator=(const DGraph& dg) {
	if (this != &dg) {

		_G = dg._G;
		_VL = dg._VL;
		_N = dg._N;
		//		_M = dg._M;
		/*)
		 _G.clear();
		 _VL.clear();

		 // assign vertices
		 for (int v=0; v<dg.number_of_vertices(); ++v)
		 {
		 add_vertex();
		 }
		 // assign edges
		 for (int v=0; v<dg.number_of_vertices(); ++v)
		 {
		 EdgeList& el = dg.edges_from(v);
		 for (EdgeList::const_iterator eit=el.begin(); eit!=el.end(); ++eit)
		 {
		 add_edge(v, *eit);
		 }
		 }
		 */
	}
	return *this;
}

Vertex& DGraph::operator[](const int vid) {
	return _VL[vid];
}

void DGraph::read_graph(istream& in) {
	string buf;
	getline(in, buf);
	if (buf != "graph_for_greach") {
		cout << "BAD FILE FORMAT!" << endl;
		exit(0);
	}

	int n;
	getline(in, buf);
	istringstream(buf) >> n;
	// initialize
	_N = n;
	_VL = VertexList(n);
	_G = GRAPH(n, InOutEdgeList());

	for (int vid = 0; vid < n; vid++) {
		add_vertex(vid);
	}

	string sub;
	int idx;
	int sid = 0;
	int tid = 0;
	while (getline(in, buf)) {
		idx = buf.find(":");
		buf.erase(0, idx + 2);
		while (buf.find(" ") != string::npos) {
			sub = buf.substr(0, buf.find(" "));
			istringstream(sub) >> tid;
			buf.erase(0, buf.find(" ") + 1);
			add_edge(sid, tid);
		}
		++sid;
	}
}

void DGraph::write_graph(ostream& out) {
	out << "Graph size = " << _G.size() << endl;
	out << "graph_for_greach" << endl;

	GRAPH::iterator git;
	EdgeList el;
	EdgeList::iterator eit;
	VertexList::iterator vit;
	int i = 0;
	for (i = 0; i < _VL.size(); i++) {
		out << i << ": ";
		el = _G[i]._outList;
		for (eit = el.begin(); eit != el.end(); eit++) {
			out << (*eit) << " ";
		}
		out << "#" << endl;
	}
}

DTree& DGraph::get_tree() {
	return _tree;
}

//NTEList& DGraph::get_NTEs()
//{
//    return _NTE;
//}

SNTEList& DGraph::get_short_NTEs() {
	return _shortNTE;
}

LNTEList& DGraph::get_long_NTEs() {
	return _longNTE;
}

void DGraph::write_tree(ostream& out) {

	_tree.write_tree(out);
}

void DGraph::write_NTEs(ostream& out) {
	//    out << endl;
	//    out << "NTEs as follows: " << endl;
	//    for (NTEList::iterator sit=_NTE.begin(); sit!= _NTE.end(); ++sit)
	//    {
	//        int src = sit->first;
	//        out << "NTEs heading from " << src << ":";
	//        EdgeList& el = sit->second;
	//        for (EdgeList::iterator tit=el.begin(); tit!=el.end(); ++tit)
	//        {
	//            int trg = *tit;
	//            out << " <" << src << "," << trg << ">";
	//        }
	//        out << endl;
	//    }
}

void DGraph::write_short_NTEs(ostream& out) {
	out << endl;
	out << "short NTEs as follows: " << endl;
	for (SNTEList::iterator sit = _shortNTE.begin(); sit != _shortNTE.end(); ++sit) {
		int src = sit->first;
		out << "short NTEs heading from " << src << ":";
		EdgeList& el = sit->second;
		for (EdgeList::iterator tit = el.begin(); tit != el.end(); ++tit) {
			int trg = *tit;
			out << " <" << src << "," << trg << ">";
		}
		out << endl;
	}
}

void DGraph::write_long_NTEs(ostream& out) {
	out << endl;
	out << "long NTEs as follows: " << endl;
	for (LNTEList::iterator sit = _longNTE.begin(); sit != _longNTE.end(); ++sit) {
		int src = sit->first;
		out << "long NTEs heading from " << src << ":";
		EdgeList& el = sit->second;
		for (EdgeList::iterator tit = el.begin(); tit != el.end(); ++tit) {
			int trg = *tit;
			out << " <" << src << "," << trg << ">";
		}
		out << endl;
	}
}

// extract all the out-going and in-going edges of all vertices
void DGraph::extract(/*hash_map*/map<int, vector<int> >& inlist, /*hash_map*/
map<int, vector<int> >& outlist) {
	for (int i = 0; i < _VL.size(); i++) {
		inlist[i] = _G[i]._inList;
		outlist[i] = _G[i]._outList;
	}
	//	printMap(inlist,outlist);
}

queue<int> DGraph::init_roots_degrees(int* outDegrees) {
	queue<int> r;
	int d;
	for (int vid = 0; vid < _N; ++vid) {
		d = out_degree_of(vid);
		if (d == 0) {
			r.push(vid);
		}
		outDegrees[vid] = d;
	}
	return r;
}

hash_map<int, int> opt_order;

bool compare(int i, int j) {
	return opt_order[i] < opt_order[j];
}

void DGraph::rearrange(hash_map<int, int>& _opt_order) {
	opt_order = _opt_order;
	for (int vid = 0; vid < _N; ++vid) {
		EdgeList& out = edges_from(vid);

		sort(out.begin(), out.end(), compare);
	}

	//rearange the roots

	roots.clear();
	for (int vid = 0; vid < _N; ++vid) {
		if (in_degree_of(vid) == 0) {
			roots.push_back(vid);
		}
	}

	sort(roots.begin(),roots.end(), compare);


	opt = true;
}


bool DGraph::reachViaTree(int i,int j){
	return _VL[i]._PreN<=_VL[j]._PreN&&_VL[i]._DFLN<=_VL[j]._DFLN;
}
